#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    static string minWindow(string s, string t) {
    //     //优化前:会超内存
    //     int hash1[100] = { 0 };
    //     int hash2[100] = { 0 };
    //     for(auto i: t) 
    //     {
    //         hash2[i - 'A']++;
    //     }
    //     int len = INT_MAX;
    //     string ret;
    //     for(int left = 0, right = 0, cnt = 0; right < s.size(); right++)
    //     {
    //         hash1[s[right]-'A']++;//进窗口
    //         if(hash1[s[right]-'A'] <= hash2[s[right]-'A']) cnt++;//进窗口后维护cnt
    //         while(cnt >= t.size())//判断：此时要求有效字符数超过t的大小
    //         {
    //             //出窗口前维护cnt
    //             if(hash1[s[left]-'A'] <= hash2[s[left]-'A']) cnt--;
    //             //出窗口
    //             hash1[s[left]-'A']--;
    //             if(len > right - left + 1)
    //             {
    //                 len = right - left + 1;
    //                 ret = s.substr(left, len);
    //             }
    //             left++;
    //         }
    //     }
    //     return ret;
    // //优化1后:依旧超内存
    //     int hash1['a' - 'A' + 53] = { 0 };
    //     int hash2['a' - 'A' + 53] = { 0 };
    //     int kinds = 0;
    //     for(auto i: t) 
    //     {
    //         if(!hash2[i - 'A'])
    //             kinds++;
    //         hash2[i - 'A']++;
    //     }
    //     int len = INT_MAX;
    //     string ret;
    //     for(int left = 0, right = 0, cnt = 0; right < s.size(); right++)
    //     {
    //         hash1[s[right]-'A']++;//进窗口
    //         if(hash2[s[right]-'A'] > 0) 
    //         {
    //             if(hash1[s[right]-'A'] == hash2[s[right]-'A']) cnt++;//进窗口后维护cnt
    //         }
    //         // cout << "s[right]: " << s[right] << " cnt: " << cnt << endl;
    //         while(cnt == kinds)//判断：此时要求有效字符种类超过t的种类
    //         {
    //             //出窗口前维护cnt
    //             if(hash1[s[left]-'A'] == hash2[s[left]-'A']) cnt--;
    //             //出窗口
    //             hash1[s[left]-'A']--;
    //             // cout << "before: " << ret << endl;
    //             if(len > right - left + 1)
    //             {
    //                 len = right - left + 1;
    //                 ret = s.substr(left, len);
    //                 // cout << "after: " << ret << endl;
    //             }
    //             left++;
    //         }
    //     }
    //     return ret;
    //优化2后:
    //     int hash1['a' - 'A' + 53] = { 0 };
    //     int hash2['a' - 'A' + 53] = { 0 };
    //     int kinds = 0;
    //     for(auto i: t) 
    //     {
    //         if(!hash2[i - 'A'])
    //             kinds++;
    //         hash2[i - 'A']++;
    //     }
    //     int len = INT_MAX;
    //     int begin = -1;
    //     for(int left = 0, right = 0, cnt = 0; right < s.size(); right++)
    //     {
    //         //进窗口
    //         if(++hash1[s[right]-'A'] == hash2[s[right]-'A']) cnt++;//进窗口后维护cnt
    //         while(cnt == kinds)//判断：此时要求有效字符种类等于t的种类
    //         {
                
    //             if(len > right - left + 1)
    //             {
    //                 len = right - left + 1;
    //                 begin = left;
    //             }
    //             //出窗口
    //             //出窗口前维护cnt
    //             if(hash1[s[left]-'A']-- == hash2[s[left]-'A']) cnt--;
    //             left++;
    //         }
    //     }
    //     if(begin == -1)
    //         return "";
    //     else
    //         return s.substr(begin, len);
    //优化三:还是以优化前的统计个数为基础进行优化
        int hash1[100] = { 0 };
        int hash2[100] = { 0 };
        for(auto i: t) 
        {
            hash2[i - 'A']++;
        }
        int len = INT_MAX;
        int begin = -1;
        for(int left = 0, right = 0, cnt = 0; right < s.size(); right++)
        {
            hash1[s[right]-'A']++;//进窗口
            if(hash1[s[right]-'A'] <= hash2[s[right]-'A']) cnt++;//进窗口后维护cnt
            while(cnt >= t.size())//判断：此时要求有效字符数超过t的大小
            {
                //出窗口前维护cnt
                if(hash1[s[left]-'A'] <= hash2[s[left]-'A']) cnt--;
                //出窗口
                hash1[s[left]-'A']--;
                if(len > right - left + 1)
                {
                    len = right - left + 1;
                    begin = left;
                }
                left++;
            }
        }
        if(begin == -1) return "";
        else return s.substr(begin, len);
    }
};

int main()
{
    string s = "ADOBECODEBANC";
    string t = "ABC";
    // string s = "a";
    // string t = "aa";
    // string s = "a";
    // string t = "a";
    cout << Solution::minWindow(s, t) << endl;
    return 0;
}